package com.xx.springboot.DataStructure.LeetCode.BST;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
     给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

     例如:
     给定二叉树: [3,9,20,null,null,15,7],

      3
     / \
     9  20
     /  \
     15   7
     返回其层次遍历结果：

     [
         [3],
         [9,20],
         [15,7]
     ]
 */
public class levelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if(root == null)
            return out;
        /**
         * 创建两个队列 一个队列用来记录 所有的父节点的值  一个队列用来记录子节点的值, 当循环完父节点, 需要将 p2 赋值给 p
         */
        Queue<TreeNode> q = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        /**
         * 将根节点 加入队列中
         */
        q.add(root);
        List<Integer> list = null;
        while (!q.isEmpty()){
            list = new ArrayList<>();

            while (!q.isEmpty()){
                TreeNode ret = q.remove();
                list.add(ret.val);
                if(ret.left != null)
                    q2.add(ret.left);
                if(ret.right != null)
                    q2.add(ret.right);
            }

            out.add(list);
            q = q2;
            q2 = new LinkedList<>();

        }
        return out;
    }
}
